package top;


import java.util.HashMap;

/**
 * @author chenyw
 * @date 2022/7/12 12:56
 * @description     复制带随机指针的链表
 *      难点在于随机指针，所以考虑哈希表存储或者使用合并再拆分
 */

public class Top138copyRandomList {
//    public Node copyRandomList(Node head) {
//        //使用hashMap
//        if (head == null) {
//            return null;
//        }
//        Node p = head;
//        HashMap<Node, Node> map = new HashMap<>();
//        while (head != null) {
//            map.put(head, new Node(head.val));
//            head = head.next;
//        }
//        head = p;
//        while (head != null) {
//            //将新节点复制给新节点
//            map.get(head).next = map.get(head.next);
//            map.get(head).random = map.get(head.random);
//            head = head.next;
//        }
//        return map.get(p);
//    }

    //使用复制合并后拆分
    //合并
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        while (cur != null) {
            Node tmp = new Node(cur.val);
            tmp.next = cur.next;
            cur.next = tmp;
            cur = cur.next.next;

        }
        cur = head;
        Node p = head.next;
        //连接随机指针跟分离链表需要两趟循环，因为后面的随机指针可能指向的是前面的链表
        //处理random
        while (p.next != null) {
            if (cur.random != null) {
                p.random = cur.random.next;
            }
            p = p.next.next;
            cur = cur.next.next;
        }
        //拆分
        cur = head;
        p = head.next;
        Node ans = p;
        while (cur != null) {
            cur.next = cur.next.next;
            if (cur.next != null) {
                p.next = cur.next.next;
            }
            cur = cur.next;
            p = p.next;
        }
        return ans;
    }

    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

}
